package com.jxb.six;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 *
 * 示例 1：
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 * 输入：n = 1
 * 输出：["()"]
 * 提示：
 * 1 <= n <= 8
 *
 * @author jiaobo
 * @date Created in 2025/1/4 14:54
 **/
public class GenerateParentheses_22 {

    public static void main(String[] args) {
        generateParenthesis(2);
    }

    public static List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans,new StringBuilder(),0,0,n);
        return ans;
    }

    /**
     * @param ans 返回的结果
     * @param cur 结果字符串
     * @param left  左括号已使用的数量
     * @param right 右括号已使用的数量
     * @param max  最大数
     * @author jiaobo
     * @date 2025/1/4 15:04
     */
    private static void backtrack(List<String> ans, StringBuilder cur, int left, int right, int max) {
        //所有括号都使用完，终止递归
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        //处理左子树
        if(left < max) {
            cur.append("(");
            backtrack(ans,cur,left+1,right,max);
            //进行回庶
            cur.deleteCharAt(cur.length() - 1);
        }
        //处理右子树
        if (right < left) {
            cur.append(")");
            backtrack(ans,cur,left,right+1,max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }

}
